As the number of data increases, scalable distributed databases have been proposed. Most of these distributed databases realize the scalability by supporting only simple query processes such as range search only in one dimension. Further, a distributed database is proposed in which range search in plural dimensions is made possible by mapping multi-dimensional values into one-dimensional values (Non-Patent Document 1 described below).
The method of the multi-dimensional range search, proposed in Non-Patent Document 1 described below, first acquires a data point indicating the maximum value (hereinafter, referred to as a maximum data point) and a data point indicating the minimum value (hereinafter, referred to as a minimum data point) from among data points obtained by changing the search target range (search space) in a multi-dimensional space having databases mapped therein, into one-dimensional range. Then, this method scans an index string in which index data for identifying respective partial spaces in the multi-dimensional space are sorted according to the order of values indicated by the data points, in a range from the minimum data point to the maximum data point. At this time, for each of the partial spaces identified on the basis of the indices within the scanning range, this method checks whether the partial space overlaps with at least part of the search space, and determines a data page associated with the overlapping partial space to be the search target.